/**
 * [154] 寻找旋转排序数组中的最小值 II
 *
 * @format
 * @lc app=leetcode.cn id=154 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
//  二分法
var findMin = function (nums) {
    const N = nums.length
    let [left, right, mid] = [0, N - 1, Math.floor(N / 2)]
    while (right - left > 1) {
        if (nums[mid] > nums[N - 1]) left = mid
        else if (nums[mid] < nums[N - 1]) right = mid
        // 处理重复元素
        else {
            let i = mid - 1
            while (i >= left) {
                if (nums[i] == nums[mid]) i--
                else if (nums[i] > nums[mid]) return nums[i + 1]
                else {
                    right = i
                    break
                }
            }
            if (i < left) left = mid
        }
        mid = Math.floor((left + right) / 2)
    }
    return Math.min(nums[left], nums[right])
}
// debugger
// const nums = [1, 3, 3]
// const MIN = findMin(nums)
// console.log(MIN)
// @lc code=end
